#include<cstdio>//uncle-lu
#include<algorithm>
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') { f|=(ch=='-'); ch=getchar(); }
	while(ch<='9'&&ch>='0') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
	x = f ? -x : x;
	return ;
}

const int Mod = 1234567;

long long int pw(long long int a)
{
	long long int temp = 2;
	long long int ans = 1;
	for(int i=a;i;i>>=1)
	{
		if(i&1)
			ans = ans * temp % Mod;
		temp *= temp;
		temp %= Mod;
	}
	return ans;
}

int main()
{
	long long int n;
	read(n);
	printf("%lld",pw(n-1));
	return 0;
}
